/*
*Copyright (c) 2012, The Linux Foundation. All rights reserved.
*Redistribution and use in source and binary forms, with or without
*modification, are permitted provided that the following conditions are
*met:
    * Redistributions of source code must retain the above copyright
      notice, this list of conditions and the following disclaimer.
    * Redistributions in binary form must reproduce the above
      copyright notice, this list of conditions and the following
      disclaimer in the documentation and/or other materials provided
      with the distribution.
    * Neither the name of The Linux Foundation nor the names of its
      contributors may be used to endorse or promote products derived
      from this software without specific prior written permission.

*THIS SOFTWARE IS PROVIDED "AS IS" AND ANY EXPRESS OR IMPLIED
*WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
*MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT
*ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS
*BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
*CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
*SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
*BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
*WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
*OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN
*IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE
*/

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <unistd.h>
#include "fsck_tree.h"
#include "fstool_common.h"
#include "fsck_boot.h"
#include "fsck_fragment.h"
#include "fsck_cache.h"

RBT_HEAD(FSCK_CACHE,FSCK_CACHE_CLUSTER_CHAIN_S);
struct FSCK_CACHE_CLUSTER_CHAIN_S* FSCK_CACHE_RBT_FIND(struct FSCK_CACHE* x, struct FSCK_CACHE_CLUSTER_CHAIN_S *y);
struct FSCK_CACHE_CLUSTER_CHAIN_S* FSCK_CACHE_RBT_REMOVE(struct FSCK_CACHE* x, struct FSCK_CACHE_CLUSTER_CHAIN_S *y);
struct FSCK_CACHE_CLUSTER_CHAIN_S* FSCK_CACHE_RBT_NEXT(struct FSCK_CACHE_CLUSTER_CHAIN_S *y);
struct FSCK_CACHE_CLUSTER_CHAIN_S* FSCK_CACHE_RBT_INSERT(struct FSCK_CACHE* x, struct FSCK_CACHE_CLUSTER_CHAIN_S *y);
struct FSCK_CACHE_CLUSTER_CHAIN_S* FSCK_CACHE_RBT_MIN(struct FSCK_CACHE* x);

int FSCK_CACHE_Cmp(FSCK_CACHE_CLUSTER_CHAIN_S *fat1, FSCK_CACHE_CLUSTER_CHAIN_S *fat2)
{
    if (fat1->head > fat2->head)
        return 1;
    else if (fat1->head < fat2->head)
        return -1;
    else
        return 0;
}

struct FSCK_CACHE g_stAllocatedCluster;

/*lint -e19 -e613*/
RBT_GENERATE(FSCK_CACHE,FSCK_CACHE_CLUSTER_CHAIN_S,rb,FSCK_CACHE_Cmp);
/*lint +e19 +e613*/

FSCK_CACHE_CLUSTER_CHAIN_S* FSCK_CACHE_NewChain(void)
{
    FSCK_CACHE_CLUSTER_CHAIN_S* pstChain = NULL;
    pstChain = calloc(1,sizeof(FSCK_CACHE_CLUSTER_CHAIN_S));
    if(!pstChain)
    {
        FSTOOL_COMM_LOG_WARN("No space\n");
        return NULL;
    }

    (void)memset_s(pstChain, sizeof(FSCK_CACHE_CLUSTER_CHAIN_S), 0x00, sizeof(FSCK_CACHE_CLUSTER_CHAIN_S));
    RBT_SET(pstChain, NULL, rb);
    return pstChain;
}

FSCK_CACHE_CLUSTER_CHAIN_S* FSCK_CACHE_FindChain(void* pstHead, FSCK_CACHE_CLUSTER_CHAIN_S* pstChain)
{
    return FSCK_CACHE_RBT_FIND((struct FSCK_CACHE*)pstHead, pstChain);
}

FSCK_CACHE_CLUSTER_CHAIN_S* FSCK_CACHE_NextChain(FSCK_CACHE_CLUSTER_CHAIN_S* pstChain)
{
    return FSCK_CACHE_RBT_NEXT(pstChain);
}


FSCK_CACHE_CLUSTER_CHAIN_S* FSCK_CACHE_InsertChain(void* pstHead, FSCK_CACHE_CLUSTER_CHAIN_S* pstChain)
{
    return FSCK_CACHE_RBT_INSERT((struct FSCK_CACHE*)pstHead, pstChain);
}
FSCK_CACHE_CLUSTER_CHAIN_S* FSCK_CACHE_MinChain(void* pstHead)
{
    return FSCK_CACHE_RBT_MIN((struct FSCK_CACHE*)pstHead);
}

void FSCK_CACHE_RemoveChain(void* pstHead, FSCK_CACHE_CLUSTER_CHAIN_S* pstChain)
{
    FSCK_CACHE_RBT_REMOVE((struct FSCK_CACHE*)pstHead , pstChain);  /*lint !e534*/
}

/****for debug**/
void FSCK_CACHE_DumpChain(FSCK_CACHE_CLUSTER_CHAIN_S* pstChain)
{
    FSCK_CACHE_S* pstCache = NULL;
    if(!pstChain)
    {
        FSTOOL_COMM_LOG_WARN("%s;NULL  pointer\n",__func__);
        return ;
    }
    FSTOOL_COMM_LOG_INFO("Cluster chain head: %u\n",pstChain->head);
    pstCache = pstChain->child;
    while (pstCache)
    {
        FSTOOL_COMM_LOG_INFO("Cluster cache [head:%u, tail:%u]\n" ,pstCache->head,pstCache->head + pstCache->length -1);
        pstCache = pstCache->next;
    }
}

/*reconvert FAT table from cluster fats when write modified FAT table to media*/

void FSCK_CACHE_SetNext(u_char* fat ,unsigned int cl ,unsigned int next)
{
    /*fat must point to the head of FAT*/
    u_char* p = NULL;
    if(!fat)
    {
        FSTOOL_COMM_LOG_ERROR("%s :No FAT table \n",__func__);
        return ;
    }
    p = fat + 4*cl;
    *p++ = (u_char)next;
    *p++ = (u_char)(next >>8);
    *p++ = (u_char)(next >> 16);
    *p &= 0xf0;
    *p |= (next >> 24) & 0x0f;
}

/* *PURPUSE: add continuous clusters to cluster fat*/
void FSCK_CACHE_Add(FSCK_CACHE_CLUSTER_CHAIN_S* pstChain , FSCK_CACHE_S* pstNewCache)
{
    struct FSCK_CACHE_S *pstCache = pstChain->child;

    if(!pstCache)
    {
        pstChain->child = pstNewCache;
        pstNewCache->next = NULL;
        pstChain->head = pstNewCache->head;
        pstChain->length = pstNewCache->length;
        return ;
    }
    /*DO NOT sort,just add to the tail*/
    while (pstCache->next)
    {
        pstCache = pstCache->next;
    }
    pstCache->next = pstNewCache;
    pstNewCache->next = NULL;
    pstChain->length += pstNewCache->length;
    return ;
}


/**PURPUSE: add a FSCK_CACHE_S to the tail of another cluster_fat_descriptor,
  be used to merge two existing cluster fat */
int FSCK_CACHE_AddToTail( FSCK_CACHE_CLUSTER_CHAIN_S* fatentry , FSCK_CACHE_S* newCache)
{
    FSCK_CACHE_S* cache = NULL;
    if(!fatentry || !newCache || !fatentry->child)
    {
        FSTOOL_COMM_LOG_WARN("%s:NULL pointer\n",__func__);
        return -1;
    }
    cache = fatentry->child;
    while (cache->next)
    {
        cache = cache->next;
    }
    cache->next = newCache;
    return 0;
}

 /*
 *Function Find_cache
 *PURPUSE: find a FSCK_CACHE_S from cluster_fat_descriptor by cluster number cl
 *PARAMETERS:
 * fat -> pointer to a cluster fat descripor
 * cl -> cluster number
 * prev_cache-> the prev FSCK_CACHE_S of OUTPUT
 *OUTPUT:
 *  return a FSCK_CACHE_S which contain cluster cl
 *NOTE:
 * if *prev_cache = return cache,that means the cache we find in cluster fat is the first one
 */
static FSCK_CACHE_S* Find_cache( FSCK_CACHE_CLUSTER_CHAIN_S* pstChain,unsigned int cl , FSCK_CACHE_S** ppstPrevCache)
{
    FSCK_CACHE_S* pstCurCache = pstChain->child;
    FSCK_CACHE_S* pstPrevCache = pstCurCache;
    while (pstCurCache)
    {
        if ( cl >= pstCurCache->head && cl < (pstCurCache->head + pstCurCache->length))
        {
            *ppstPrevCache = pstPrevCache;
            return pstCurCache;
        }
        pstPrevCache = pstCurCache;
        pstCurCache = pstCurCache->next;
    }
    return NULL;
}

/*
 *Function FSCK_CACHE_Next
 *PURPUSE: find the next cluster number of clus
 *PARAMETERS:
 * fat -> pointer to a cluster fat descripor
 * clus -> find the next cluster of cluster number clus
 * cl -> the next cluster number will returned
 *OUTPUT:
 *  return a FSCK_CACHE_S which contain the next cluster
 *NOTE:
 * if returned FSCK_CACHE_S is null and *cl = 0 ,that means DON'T find the next cluster from the given cluster fat
 * if returned FSCK_CACHE_S is null but *cl != 0 ,that means clus is the last cluster of the given cluster fat
 */
FSCK_CACHE_S* FSCK_CACHE_Next( FSCK_CACHE_CLUSTER_CHAIN_S* pstChain,unsigned int clus, unsigned int* cl)
{
    struct FSCK_CACHE_S* cache = pstChain->child;
    *cl = 0x0;
    if(!cache)
    {
        FSTOOL_COMM_LOG_WARN("Not find the cluster after cluster %d\n",clus);
        return (struct FSCK_CACHE_S*)0;
    }

    while (cache)
    {
        if (clus >= cache->head && clus <= cache->head + cache->length -2 )
        {
            *cl =  clus + 1;
            return cache;
        }
        if (clus == cache->head + cache->length -1 )
        {
            cache = cache->next;
            if (cache)
            {
                *cl = cache->head;
                return cache;
            }else
            {
                *cl = FSTOOL_COMM_CLUSTER_EOF;
                return (struct FSCK_CACHE_S*)0;
            }
        }
        cache = cache->next;
    }
    return NULL;
}

/*
 *Function FATCACHE_Trunc
 *PURPUSE: delete all the FSCK_CACHE_S below a given FSCK_CACHE_S in a given cluster fat
 *PARAMETERS:
 * fatentry -> pointer to a cluster fat descripor
 * cache -> the FSCK_CACHE_S whose below FSCK_CACHE_S will be removed
 */
static int FATCACHE_Trunc(FSCK_CACHE_CLUSTER_CHAIN_S* pstChain, FSCK_CACHE_S*cache)
{
    struct FSCK_CACHE_S *curr = cache;
    struct FSCK_CACHE_S *next = NULL;
    struct FSCK_CACHE_S *last = NULL;
    struct FSCK_FRAGMENT_S *frag = NULL;
    struct FSCK_FRAGMENT_S *insert = NULL;

    last = cache;
    if(!cache || !pstChain)
    {
        FSTOOL_COMM_LOG_WARN("%s:NULL pointer\n",__func__);
        return -1;
    }
    next = curr->next;
    if (!next)
    {
        return 0;
    }

    while (next)
    {
        curr = next;
        next = next->next;
        pstChain->length -= curr->length;
        frag = FSCK_FRAGMENT_New();
        if(!frag)
        {
            FSTOOL_COMM_LOG_ERROR("%s: No space left\n",__func__);
            goto memoryFree;
        }
        /*when clear chain or FSCK_CACHE_Trunc ,move this cluster cache to free tree for FSCK_FAT_Write()*/
        frag->head = curr->head;
        frag->length = curr->length;
        insert = FSCK_FRAGMENT_Insert(&g_stFreeCluster, frag);
        if (insert)
        {
            FSTOOL_COMM_LOG_WARN("%s:FSCK_FRAGMENT_S(head:0x%x) exist\n",__func__,frag->head);
            free(frag);
            frag = NULL;
        }
memoryFree:
        free((void*)curr);
    }
    last->next = NULL;
    return 0;
}

/*
 *Function FSCK_CACHE_Trunc
 *PURPUSE: delete all the clusters after cl from a given cluster fat
 *PARAMETERS:
 * fat -> pointer to a cluster fat descripor
 * cl -> the cluster whose below clusters will be removed
 *NOTE: this function was used to handle the issue when a file has incorrect cluster numbers
 */
void FSCK_CACHE_Trunc(FSCK_BOOT_SECTOR_S* pstBoot, FSCK_CACHE_CLUSTER_CHAIN_S* pstChain, unsigned int cl)
{
    FSCK_CACHE_S* pstPrevCache = NULL;
    FSCK_CACHE_S* pstCurCache = Find_cache(pstChain,cl,&pstPrevCache);
    struct FSCK_FRAGMENT_S *frag = NULL;
    unsigned int currlen = 0;
    unsigned int org_chain_len = pstChain->length;

    FSTOOL_COMM_LOG_WARN("cluster chain :%u , cl to truncate : %d \n",pstChain->head,cl);

    if(!pstCurCache)
    {
        return;
    }
    FATCACHE_Trunc(pstChain,pstCurCache);   /*lint !e534*/
    currlen = cl - pstCurCache->head + 1;
    if (currlen != pstCurCache->length)
    {
        frag = FSCK_FRAGMENT_New();
        if(!frag)
        {
            FSTOOL_COMM_LOG_ERROR("%s ,No space left\n",__func__);
            goto re_calc;
        }

        frag->head = cl + 1;
        frag->length = pstCurCache->length - currlen;
        if (FSCK_FRAGMENT_Insert(&g_stFreeCluster, frag))
        {
            FSTOOL_COMM_LOG_INFO("%s:FSCK_FRAGMENT_S(head:%u) exist\n",__func__,frag->head);
            free(frag);
            frag = NULL;
        }
    }
re_calc:
    pstChain->length -= (pstCurCache->length - currlen);
    pstCurCache->length = currlen;
    pstBoot->NumFree += (org_chain_len - pstChain->length);
}   /*lint !e438*/

/*
 * This is a trade-off between time and memory
 * In order to reduce the runtime memory consumption
 * We change the whole strategy of cluster chain checking
 * and managment.
 * In some extreme cases, most of the clusters in FAT file
 * system are discrete. that means it will take much time
 * to manage memory and cluster chain at runtime.
 * So set a limitation of max memory malloc here.
 */

FSCK_CACHE_S* FSCK_CACHE_New(void)
{
    struct FSCK_CACHE_S *cache= NULL;
    cache = calloc(1,sizeof(struct FSCK_CACHE_S));
    if (!cache)
    {
        FSTOOL_COMM_LOG_ERROR("No space \n");
        return NULL;
    }

    (void)memset_s(cache, sizeof(FSCK_CACHE_S), 0x00, sizeof(FSCK_CACHE_S));
    return cache;
}

void FSCK_CACHE_Free(void* pstHead)
{
    struct FSCK_CACHE_CLUSTER_CHAIN_S* pstChain = NULL;
    struct FSCK_CACHE_CLUSTER_CHAIN_S* pstNextChain = NULL;
    struct FSCK_CACHE_S *cache = NULL;
    struct FSCK_CACHE_S *next_cache = NULL;
    FSTOOL_COMM_LOG_INFO("%s \n",__func__);
    pstChain = FSCK_CACHE_RBT_MIN((struct FSCK_CACHE*)pstHead);
    if(!pstChain)
    {
        FSTOOL_COMM_LOG_INFO("%s :rb tree is empty\n",__func__);
        return ;
    }
    while (pstChain)
    {
        cache = pstChain->child;
        if(!cache)
        {
            continue;
        }
        while (cache)
        {
            next_cache = cache->next;
            free(cache);
            cache = next_cache;
        }
        pstNextChain = FSCK_CACHE_RBT_NEXT(pstChain);
        /*must remove from rb tree before free*/
        FSCK_CACHE_RBT_REMOVE((struct FSCK_CACHE*)pstHead,pstChain);    /*lint !e534*/
        free(pstChain);
        pstChain = pstNextChain;
    }
}
